#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>
using namespace std;

typedef int keytype;

void adjust_heap(vector<keytype> &keys, int low, int high)
{
  int i;
  bool flag;
  keytype k;

  k = keys[low];
  flag = true;
  for (i = 2*low; i <= high && flag; i*=2){
    if (i < high && keys[i+1] > keys[i]) i++;
    if (k < keys[i]){
      keys[low] = keys[i];
      low = i;
    }
    else flag = false;
  }
  keys[low] = k;
}

void heap(vector<keytype> &keys)
{
  int i;
  keytype t;

  for (i = (keys.size()-1)/2; i >= 1; i--)
    adjust_heap(keys, i, keys.size()-1);

  for (i = keys.size()-1; i >= 1; i--){
    t = keys[1];
    keys[1] = keys[i];
    keys[i] = t;
    adjust_heap(keys, 1, i-1);
  }
}

void print(vector<keytype> &keys)
{
  for (auto it = keys.begin()+1; it != keys.end(); it++)
    cout << *it << "\t";
  cout << endl;
}

int main()
{
  ifstream in("sort.txt");
  vector<keytype> keys;
  keytype k;

  assert(in);
  keys.push_back(0);
  while (in >> k)
    keys.push_back(k);

  heap(keys);
  print(keys);
  in.close();

  return 0;
}
